﻿#include <QDebug>
#include "libNCACore_global.h"
#include "sentence.h"
#include "literals/delta.h"
#include "literals/bracket.h"
#include "expression.h"

Sentence::Sentence()
  :_coefficient(1)
  {
  }

Sentence::~Sentence()
  {
  cleanup();
  }

void Sentence::cleanup()
  {
  for (int i = 0; i < size(); i++)
    delete at(i);
  clear();
  _coefficient = 1;
  }

Sentence::Sentence(Sentence&& s)
  {
  for (int i = 0; i < s.size(); ++i)
    append(s[i]);
  s.clear();
  _coefficient = s.getCoefficient();
  }

Sentence& Sentence::operator=(Sentence &&rhs)
  {
  if (this == &rhs)
    return *this;

  _coefficient = rhs._coefficient;
  if (size() != removeWords(0, size()))
    qWarning() << "Not all words were cleared before added new. Number of removed words: " ;
  for (int i = 0; i < rhs.size(); ++i)
    append(rhs[i]);
  rhs.clear();
  return *this;
  }

Sentence::Sentence(const Sentence& s)
  : QList<Word*>()  // we'll take care of copying data by ourselves
  {
  for (int i = 0; i < s.size(); ++i)
    {
    Word *w = s.at(i)->createCopy();
    insert(size(), w);
    }
  _coefficient = s.getCoefficient();
  }

Sentence& Sentence::operator=(const Sentence &rhs)
  {
  if (this == &rhs)
    return *this;

  _coefficient = rhs._coefficient;
  if (size() != removeWords(0, size()))
    qWarning() << "Not all words were cleared before added new. Number of removed words: " ;
  for (int i = 0; i < rhs.size(); ++i)
    {
    Word *w = rhs.at(i)->createCopy();
    insert(size(), w);
    }
  return *this;
  }

bool Sentence::operator== (const Sentence &other) const
  {
  if (size() != other.size())
    return false;

  for (int i = 0; i < size(); i++)
    {
    if (*(at(i)) != *(other.at(i)))
      return false;
    }
  return (other._coefficient == this->_coefficient); // words are the same so only coefficient should be checked
  }

bool Sentence::compareWithoutCoefficient(const Sentence &other) const
  {
  if (size() != other.size())
    return false;

  for (int i = 0; i < size(); i++)
    {
    if (*(at(i)) != *(other.at(i)))
      return false;
    }
  return true;
  }

bool Sentence::operator!= (const Sentence &other) const
  {
  return !(*this == other);
  }

int Sentence::removeWords(int startingWord, int count)
  {
  int deleted = 0;
  while ((startingWord >= 0) && (startingWord < size()) && (deleted < count))
    {
    delete (at(startingWord));
    removeAt(startingWord);
    deleted++;
    }
  return deleted;
  }

void Sentence::appendWordsFromSentence(Sentence const& other, int startingWord, int count)
  {
  int barrier = startingWord + count;
  if (count + startingWord > other.size())
    barrier = other.size();
  for (int i = startingWord; i < barrier; i++)
    insert(startingWord++, other.at(i)->createCopy());
  }

void Sentence::concatenate(Sentence const& other)
  {
  for (int i = 0; i < other.size(); i++)
    this->insert(size(), other.at(i)->createCopy());
  _coefficient *= other.getCoefficient();
  }

// algorithm for LongestCommonSubstring taken from wiki
// http://en.wikibooks.org/wiki/Algorithm_implementation/Strings/Longest_common_substring#C.2B.2B
int Sentence::getCommonPart(const Sentence pattern, Sentence& commonPart) const
  {
  commonPart.clear();
  if (size() == 0 || pattern.size() == 0)
    return -1;

  int *curr = new int [pattern.size()];
  int *prev = new int [pattern.size()];
  int *swap = NULL;
  int maxSubstr = 0;
  int lastSubsBegin = 0;

  for (int i = 0; i < this->size(); ++i)
    {
    for (int j = 0; j < pattern.size(); ++j)
      {
      if (*at(i) != *pattern.at(j))
        curr[j] = 0;
      else
        {
        if(i == 0 || j == 0)
          curr[j] = 1;
        else
          curr[j] = 1 + prev[j-1];
        if (maxSubstr < curr[j])
          {
          maxSubstr = curr[j];
          int thisSubsBegin = i - curr[j] + 1;
          if (lastSubsBegin == thisSubsBegin)
            {//if the current LCS is the same as the last time this block ran
            commonPart.appendWordsFromSentence(*this, i, 1);
            }
          else //this block resets previous LCS if a different LCS is found
            {
            lastSubsBegin = thisSubsBegin;
            commonPart.clear();
            commonPart.appendWordsFromSentence(*this, lastSubsBegin, (i + 1) - lastSubsBegin);
            }
          }
        }
      }
    swap = curr;
    curr = prev;
    prev = swap;
    }
  delete [] curr;
  delete [] prev;

  // one more thing: coefficients
  double fGcd = gcd(pattern.getCoefficient(), _coefficient);
  if (fGcd > 1)
    commonPart.setCoefficient(fGcd);

  return lastSubsBegin;
  }

double Sentence::getCoefficient() const
  {
  return _coefficient;
  }

int Sentence::countWordType(Word::Type type) const
  {
  int nType = 0;
  for (int i = 0; i < this->size(); ++i)
    {
    if (at(i)->getType() == type)
      nType++;
    if (at(i)->getType() == Word::WT_BRACKET)
      nType += dynamic_cast<Bracket*>(at(i))->countWordType(type);
    }
  return nType;
  }

// Function returns index of first occurence of a type.
// Returns -1, if there is no such type.
int Sentence::firstOccurrenceOfType(Word::Type type) const
  {
  for (int i = 0; i < size(); i++)
    {
    if (at(i)->getType() == type)
      return i;
    }
  return -1;
  }

void Sentence::setCoefficient(double coefficient)
  {
  _coefficient = coefficient;
  }

Sentence Sentence::getSubsentenceOfType(Word::Type type) const
  {
  Sentence ret;
  for (int i = 0; i < size(); i++)
    if (at(i)->getType() == type)
      ret.insert(ret.size(), at(i)->createCopy());
  ret.setCoefficient(_coefficient);
  return ret;
  }

//Delta source is delta with smallest left label
bool Sentence::doDeltaTrick()
  {
  int deltaCount = countWordType(Word::WT_DELTA);
  if (0 == deltaCount)
    return false;
  int firstDeltaIndex = firstOccurrenceOfType(Word::WT_DELTA);
  QString smallestLabel, removingLabel;
  int sourceDeltaIndex;
  bool changed = false;

  for (int dc = firstDeltaIndex; dc < deltaCount; dc++)
    {
    smallestLabel = at(dc)->getLabels().at(0);
    removingLabel = at(dc)->getLabels().at(1);
    sourceDeltaIndex = dc;
    // 1. Find the smallest label
    for (int i = firstDeltaIndex+1; i < deltaCount; i++)
      {
      if (at(i)->getType() != Word::WT_DELTA)
        {
        qWarning() << "Deltas should be next to each other before delta trick!";
        return false;
        }
      if ((smallestLabel.compare(at(i)->getLabels()[0]) > 0) && (at(i)->getLabels().at(0).compare(at(i)->getLabels().at(1)) != 0) )
        {
        smallestLabel = at(i)->getLabels().at(0);
        removingLabel = at(i)->getLabels().at(1);
        sourceDeltaIndex = i;
        }
      }
    if (at(dc)->getLabels().at(0).compare(at(dc)->getLabels().at(1)) == 0)
      continue;
    // 2. Move source delta on place dc
    swap(sourceDeltaIndex, dc);
    sourceDeltaIndex = dc;
    if (sourceDeltaIndex != dc)
      changed = true;
    //3. Foreach word in sentence (except delta_source) replace removingLabel and smallestLabel
    for (int i = 0; i < size(); i++)
      {
      if (i == sourceDeltaIndex)
        continue;
      for (int j = 0; j < at(i)->getLabels().size(); j++)
        if (removingLabel.compare(at(i)->getLabels().at(j)) == 0)
          {
          at(i)->setLabel(j, smallestLabel);
          changed = true;
          }
      }
    }
  changed |= sortType(firstDeltaIndex, deltaCount, Word::WT_DELTA);
  return changed;
  }

/*
 * Correct order of word types in a sentence:
 *   0. Coefficients - we do not care about them here, because practically they are not a Word
 *   1. Variables
 *   2. Deltas
 *   3. Functions
 *   4. Operators - we can't move them! They will be left at the end as a result of previous operations.
 *
 * @return true, if Sentence was changed in the process.
 */
bool Sentence::groupTypes()
  {
  int const numOfVariables = countWordType(Word::WT_VARIABLE);
  int const numOfDeltas = countWordType(Word::WT_DELTA) + numOfVariables;
  int const numOfFunctions = countWordType(Word::WT_FUNCTION) + numOfDeltas;

  bool checkAgain = true; //if sth was changed in the loop check again
  bool changed = false;

  while (checkAgain)
    {
    checkAgain = false;
    for (int i = 0; i < size(); i++)
      {
      switch (static_cast<int>(at(i)->getType()))
        {
        case Word::WT_VARIABLE:
          if (i > numOfVariables)
            {
            move(i, 0);
            checkAgain = true;
            changed = true;
            }
          break;
        case Word::WT_DELTA:
          if ((i >= (numOfDeltas) ) || (i < numOfVariables))
            {
            move(i, numOfVariables);
            changed = true;
            checkAgain = true;
            }
          break;
        case Word::WT_FUNCTION:
          if ((numOfDeltas != i) && ( (i >= numOfFunctions ) || (i < numOfDeltas )))
            {
            move(i, numOfDeltas);
            changed = true;
            checkAgain = true;
            }
          break;
        case Word::WT_BRACKET:
          // TODO: issue 51
          dynamic_cast<Bracket*>(at(i))->sort();
          break;
        case Word::WT_OPERATOR:
          break;
        default:
          qWarning() << "This word "<< at(i) << " is unknown type " <<at(i)->getType();
        }
      }
    }

  if (numOfVariables > 1)
    changed |= sortType(0, numOfVariables, Word::WT_VARIABLE);
  if (numOfDeltas-numOfVariables > 1)
    changed |= sortType(numOfVariables, numOfDeltas-numOfVariables, Word::WT_DELTA);
  if (numOfFunctions-numOfDeltas > 1)
    changed |= sortType(numOfDeltas, numOfFunctions-numOfDeltas, Word::WT_FUNCTION);

  return changed;
  }


 /*
  * Sorts words of a given type.
  * Words should be grouped. Behaviour if they are not, is undefined.
  * @params index - position of a first word from the group
  * @params count - number of words in the group
  */
bool Sentence::sortType(const int index, const int count, Word::Type type)
  {
  bool changed = false;
  if (count > size() || index < 0 || index > size() || at(index)->getType() != type )
    {
    qWarning() <<"Wrong data given to sortType";
    return false;
    }
  for (int i = index+1, j = i; i < index+count; i++)
    {
    j = i;
    while ((j > 0) && (at(j-1)->getType() == type) && (at(j-1)->isGreaterThan(*at(j))))
      {
      swap(j, j-1);
      j--;
      changed = true;
      }
    }
  return changed;
  }

bool Sentence::isGreaterThan(const Sentence& other) const
  {
  for (int i = 0; i < size(); i++)
    if (*at(i) != *other.at(i))
      return at(i)->isGreaterThan(*other[i]);
  return false;
  }
